package daybook.util.tree;

import daybook.annotation.Bean;
import org.immutables.value.Value;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

@Bean
@Value.Immutable
public abstract class Tree<T> implements Iterable<T> {
    @Value.Parameter
    public abstract T getValue();
    @Value.Parameter
    public abstract List<Tree<T>> getChildren();

    public boolean isLeaf() {
        return getChildren().isEmpty();
    }


    public static <T> Tree<T> of(T val) {
        return ImmutableTree.of(val, Collections.emptyList());
    }

    // 从左到右的广度优先搜索
    private static class TreeIterator<T> implements Iterator<T> {
        private final Deque<Tree<T>> queue;

        private TreeIterator(Tree<T> tree) {
            Objects.requireNonNull(tree);
            queue = new ArrayDeque<>();
            queue.offer(tree);
        }

        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override
        public T next() {
            // get first element, if doesn't have first element throws NoSuchElementException
            final Tree<T> tree = queue.pop();
            // append elements
            queue.addAll(tree.getChildren());
            return tree.getValue();
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new TreeIterator<>(this);
    }

    public Stream<T> stream() {
        return StreamSupport.stream(Spliterators.spliteratorUnknownSize(
                iterator(),
                Spliterator.ORDERED | Spliterator.IMMUTABLE), false);
    }

    private static class LeafIterator<T> implements Iterator<T> {
        private final Deque<Tree<T>> queue;

        private LeafIterator(Tree<T> tree) {
            Objects.requireNonNull(tree);
            queue = new ArrayDeque<>();
            queue.offer(tree);
        }

        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override
        public T next() {
            Tree<T> tree;

            do {
                // get first element, if doesn't have first element throws NoSuchElementException
                tree = queue.pop();
                // append elements
                queue.addAll(tree.getChildren());
            } while (!tree.isLeaf());

            return tree.getValue();
        }
    }

    public Iterator<T> leafIterator() {
        return new LeafIterator<>(this);
    }

    public Stream<T> leafStream() {
        return StreamSupport.stream(Spliterators.spliteratorUnknownSize(
                leafIterator(),
                Spliterator.ORDERED | Spliterator.IMMUTABLE), false);
    }

    public static <T> Tree<T> buildTree(T parent, Map<T, List<T>> mapTree) {
        final List<T> children = mapTree.get(parent);
        if (children == null || children.isEmpty()) {
            return Tree.of(parent);
        } else {
            return ImmutableTree.of(parent, children.stream()
                    .map(p -> buildTree(p, mapTree))
                    .collect(Collectors.toList()));
        }
    }
}
